COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00005 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A94.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 29, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Example for CS254:  composites (in unary) are not pumpable.}

We prove $L = \{ a↑{(i)}\mid i\,\hbox{is composite}\}$ is not a CFL.
Suppose it were, and that $n$ were the pumping number of $L$.  Let $\lambda (x)$
be the least common multiple of $(1:x)$.  Then, if $x \geq 2$, $(\lambda
(x) + 2 : \lambda(x) + x)$ is a sequence of $x-1$ consecutive composite
numbers.  In particular, $x = \lambda(n) + 1$,
$$(\lambda (\lambda(n) + 1) + 2 : \lambda (\lambda (n) + 1) + \lambda (n)
+ 1)$$
is a sequence of $\lambda (n)$ consecutive composite numbers.  Let $p$ be the
next larger prime number (Euclid showed that there is one), so
$p \geq\lambda (\lambda (n) + 1) + \lambda (n) + 2$.  Then $c = p - \lambda
(n) \geq \lambda (\lambda (n) + 1) + 2$ is composite, and $a↑{(c)} \in L$.
Pumping $a↑{(c)}$ adds $d$ characters, $1 \leq d\leq n$, and pumping
$\lambda (n)/d$ times adds $\lambda (n)$ characters, giving
$a↑{(c + \lambda (n))} = a↑{(p)}$.  But $a↑{(p)} \notin L$, a contradiction.
More generally, if a CFL has strings of all large composite lengths, it has
infinitely many strings of prime length.
\bye